package test7;

public class Demo8 {
    public static void main(String[] args) {
        int[][] grid = {
                {1, 1, 1, 1, 1, 1, 1},
                {1, 0, 0, 0, 0, 0, 1},
                {1, 0, 1, 1, 1, 0, 1},
                {1, 0, 1, 0, 1, 0, 1},
                {1, 0, 1, 1, 1, 0, 1},
                {1, 0, 0, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 1, 1}
        };

        System.out.println(numIslands(grid));
    }

    public static int numIslands(int[][] grid) {
        int res = 0;
        int m = grid.length, n = grid[0].length;
        for (int j = 0; j < n; j++) {
            // 把靠上边的岛屿淹掉
            dfs(grid, 0, j);
            // 把靠下边的岛屿淹掉
            dfs(grid, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            // 把靠左边的岛屿淹掉
            dfs(grid, i, 0);
            // 把靠右边的岛屿淹掉
            dfs(grid, i, n - 1);
        }
        //遍历
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    static void dfs(int[][] grad, int i, int j) {
        int m = grad.length, n = grad[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) {
            return;
        }
        //将岛屿全部进行淹没
        if (grad[i][j] == 1) {
            return;
        }
        grad[i][j] = 1;
        dfs(grad, i - 1, j);
        dfs(grad, i + 1, j);
        dfs(grad, i, j - 1);
        dfs(grad, i, j + 1);
    }

}
